/*******************************************

  TRABALHO DE CONCORRENTES - PROJETO 2

  Hospital ICMCTown

  Alunos:
    Caio André Rodrigues        7656411
    Cesar Bonelli Milano        7288939
    Roberty Manzini Bertolo     7573399

********************************************/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#include <assert.h>
#include <omp.h>

#define INFINITE    1000000000
#define THREAD      4

/**
  readNumJuncoes()
  Le o numero de Juncoes
**/
int readNumJuncoes()
{
    int numJuncoes;

    scanf("%d", &numJuncoes);
    if( !((numJuncoes >= 2) && (numJuncoes <= 1000)) )
    {
      printf("-----------\nNumero de Juncoes nao esta no intervalo especificado.\n-----------\n\n");
      abort();
    }

    return numJuncoes;
}

/**
  readNumLinhas(int numJuncoes)
  Le o numero de Linhas
**/
int readNumLinhas(int numJuncoes)
{
    int numLinhas;

    scanf("%d", &numLinhas);
    if( !((numLinhas >= (numJuncoes-1)) && ( numLinhas <= ((numJuncoes*(numJuncoes-1))/2))) )
    {
      printf("-----------\nNumero de Linhas nao esta no intervalo especificado.\n-----------\n\n");
      abort();
    }

    return numLinhas;
}

/**
  defineJuncoes(a,b,i);
**/
void defineJuncoes(int *a, int *b, int i, int numJuncoes)
{
    scanf("%d", &a[i]);
    if( !(a[i] >= 1 && a[i] <= numJuncoes) ) printf("-----------\nJuncao nao esta existe.\n-----------\n\n"), abort();

    scanf("%d", &b[i]);
    if( !(b[i] >= 1 && b[i] <= numJuncoes) ) printf("-----------\nJuncao nao esta existe.\n-----------\n\n"), abort();
    if( a[i] == b[i] ) printf("-----------\nJuncoes iguais.\n-----------\n\n"), abort();
}

/**

**/
void distanciaJuncoes(int *w, int i)
{
    scanf("%d", &w[i]);
    if( !(w[i] >= 1 && w[i] <= 100000) ) printf("-----------\nTamanho do caminho nao esta no intervalo especificado.\n-----------\n\n"), abort();
}

/**

**/
void montarGrafo(int *a, int *b, int *w, int numJuncoes, int numLinhas, int **grafo)
{
    int i, j;

    for(i=0;i<numLinhas;i++)
    {
        grafo[a[i]-1][b[i]-1] = w[i];
        grafo[b[i]-1][a[i]-1] = w[i];
    }
}


// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], int numJuncoes, bool sptSet[])
{
   // Initialize min value
   int min = INT_MAX, min_index;
    int v;
   for (v = 0; v < numJuncoes; v++)
     if (sptSet[v] == false && dist[v] <= min)
         min = dist[v], min_index = v;

   return min_index;
}

// A utility function to print the constructed distance array
int printSolution(int dist[], int numJuncoes)
{
    int i;
   //printf("Vertex   Distance from Source\n");
   for (i = 0; i < numJuncoes; i++)
      printf("%d \t\t %d\n", i, dist[i]);
}

int maximo(int dist[], int numJuncoes)
{
   int i, aux=0;
   //aprintf("Vertex   Distance from Source\n");
   for (i = 0; i < numJuncoes; i++)
      if(dist[i] > aux) aux = dist[i];
    return aux;
}

// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
int dijkstra(int **graph, int numJuncoes, int src)
{
  int i, count,v;
     int dist[numJuncoes];     // The output array.  dist[i] will hold the shortest
                      // distance from src to i

     bool sptSet[numJuncoes]; // sptSet[i] will true if vertex i is included in shortest
                     // path tree or shortest distance from src to i is finalized

     // Initialize all distances as INFINITE and stpSet[] as false
     for (i = 0; i < numJuncoes; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

     // Distance of source vertex from itself is always 0
     dist[src] = 0;

     // Find shortest path for all vertices
     for (count = 0; count < numJuncoes-1; count++)
     {
       // Pick the minimum distance vertex from the set of vertices not
       // yet processed. u is always equal to src in first iteration.
       int u = minDistance(dist, numJuncoes, sptSet);

       // Mark the picked vertex as processed
       sptSet[u] = true;

       // Update dist value of the adjacent vertices of the picked vertex.

       for (v = 0; v < numJuncoes; v++)

         // Update dist[v] only if is not in sptSet, there is an edge from
         // u to v, and total weight of path from src to  v through u is
         // smaller than current value of dist[v]
         if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                                       && dist[u]+graph[u][v] < dist[v])
            dist[v] = dist[u] + graph[u][v];

     }

     // print the constructed distance array
     //printSolution(dist, numJuncoes);
     return maximo(dist,numJuncoes);
}


/******************
Função Principal
*******************/
int main()
{
    int numLinhas, numJuncoes;
    int *a,*b,*w;     // a[] e b[]  numero das juncoes
                      // w[]        distancia das juncoes
    int *min;
    int aux=INFINITE;

    int i;            // contador
    int j;

    int **grafo;

    numJuncoes = readNumJuncoes();
    numLinhas = readNumLinhas(numJuncoes);

    a = (int *) calloc(numLinhas,sizeof(int));
    b = (int *) calloc(numLinhas,sizeof(int));
    w = (int *) calloc(numLinhas,sizeof(int));
    min = (int *) calloc(numJuncoes,sizeof(int));

    for(i=0;i<numLinhas; i++)
    {
        defineJuncoes(a,b,i,numJuncoes);
        distanciaJuncoes(w,i);
        //printf("a[i]: %d b[i]: %d w[i]:%d \n", a[i],b[i],w[i]);
    }


    grafo = (int **) calloc(numJuncoes,sizeof(int *));
    for(i=0;i<numJuncoes+1;i++) grafo[i] = (int *) calloc(numJuncoes,sizeof(int));


    montarGrafo(a,b,w,numJuncoes,numLinhas,grafo);

    /*for(i=0;i<numJuncoes;i++)
    {
      for(j=0;j<numJuncoes;j++)
        printf("%d ",grafo[i][j]);
      printf("\n");
    }
    */
    #pragma omp parallel num_threads(THREAD)
    {
      #pragma omp for
      for(i=0;i<numJuncoes;i++)
      {
        //printf("---------------\n");
        //printf("Solution %d:\n", i+1);
        min[i] = dijkstra(grafo, numJuncoes, i);
        //printf("%d \n", min[i]);
      }

      #pragma omp for
      for(i=0;i<numJuncoes;i++)
        if(min[i] < aux) aux = min[i];
    }

    printf("%d\n", aux);

    return 0;
}
